package leetcode.N1_N100;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/10 11:41 上午
 */
public class N31 {

    /**
     * 1.从尾部往前遍历，寻找第一个非升序元素
     * 2.将其与已经遍历过得元素中大于且最接近的元素换位
     * 3.将非升序元素后续的元素反转
     * 4.若第一步中没找到这个元素  则将整个数组反转
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        // 1.寻找非升序元素下标
        int endIndex = nums.length - 1;
        int index = endIndex - 1;
        int lastVal = nums[endIndex];
        for (; index >= 0; index--) {
            if (nums[index] < lastVal) {
                break;
            }
        }
        // 2.存在非升序元素 index >= 0  变换位置
        int biggerIndex = endIndex;
        if (index >= 0) {
            for (int i = index; i <= endIndex; i++) {
                if (nums[i] < nums[index]) {
                    biggerIndex = i - 1;
                    break;
                }
            }
        }
        int temp = nums[biggerIndex];
        nums[biggerIndex] = nums[index];
        nums[index] = temp;

        // 3.反转 从index + 1 到endIndex的数组
        for (int left = index + 1, right = endIndex; left < right; left++, right--) {
            int t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
        }
    }
}
